/**
 * @Description: 实现 strStr()
 * 给你两个字符串 haystack 和 needle ，
 * 请你在 haystack 字符串中找出 needle
 * 字符串出现的第一个位置（下标从 0 开始）。如果不存在，则返回  -1 。
 * <p>
 * 说明：
 * 当 needle 是空字符串时，我们应当返回什么值呢？
 * 这是一个在面试中很好的问题。
 * 对于本题而言，当 needle 是空字符串时我们应当返回 0 。
 * 这与 C 语言的 strstr() 以及 Java 的 indexOf() 定义相符。
 * @Date:Create in 16:24  2022/7/8
 */
public class strStr0028 {

    public static void main(String[] args) {
        String haystack = "aaaaa";
        String needle = "aaaaaa";
        System.out.println(strStr2(haystack, needle));
    }

    //暴力解法
    public static int strStr1(String haystack, String needle) {
        if (needle.equals("")) return 0;

        char[] ch1 = haystack.toCharArray();
        char[] ch2 = needle.toCharArray();
        int left = 0, right = 0;
        out:
        for (int i = 0; i < ch1.length; i++) {
            if (ch1[i] == ch2[0]) {
                left = i;
                right = i;
                int j = 0;
                while (j < ch2.length) {
                    System.out.println(right);
                    if (right >= ch1.length) break out;
                    if (ch1[right] == ch2[j]) {
                        right++;
                        j++;
                    } else {
                        continue out;
                    }
                }
                return left;
            }
        }
        return -1;
    }

    //KMP方法
    public static int strStr2(String haystack, String needle) {
        if (needle.length() == 0) return 0;
        int[] next = new int[needle.length()];
        getNext(next, needle);

        int j = 0;
        for(int i=0;i<haystack.length();i++){
            while(j>0 && needle.charAt(j)!=haystack.charAt(i)) j = next[j-1];
            if(needle.charAt(j) == haystack.charAt(i)) j++;
            if(j==needle.length()) return i-needle.length()+1;
        }
        return -1;
    }

    //获取前缀表
    public static void getNext(int[] next, String s) {
        int j = 0;
        next[0] = 0;
        for (int i = 1; i < s.length(); i++) {
            while (j > 0 && s.charAt(j) != s.charAt(i)) j = next[j - 1];
            if (s.charAt(j) == s.charAt(i)) j++;
            next[i] = j;
        }
    }
}
